Speicher ist ein begrenztes und (vor allem als Ram) teures Betriebsmittel. Besonders in einem Multitaskingsystem, in dem der Speicher auch noch unter mehreren Prozessen aufgeteilt werden muß, kommt es leicht zu Verknappungen. Besonders speicherintensive Anwendungen wie Graphik, DTP und aufwendige Hochsprachencompiler tragen ein weiteres hierzu bei.
Die Lösung bestünde nun darin, die Rechner bis zum Platzen mit Ram zu bestücken. Doch ist dies erstens ziemlich teuer und zweitens meistens nicht ausreichend (ein 24 Bit Bild mit 4000x4000 Punkten braucht allein bereits 64MByte).
Deshalb ist es bei Multiuser-Betriebssystemen, wie z.B. UNIX, schon lange üblich, einen Teil des Rams auf eine Partition oder in ein File einer Festplatte auszulagern, und nur bei Bedarf in den echten Systemspeicher zu laden. Man nennt diesen ausgelagerten Speicher auch virtuellen Speicher.
2. Wie geht's
Das Prinzip ist mit dem eines Cachespeichers vergleichbar (man nennt es auch Speicherhierarchie). Auf der Festplatte wird ein großes File (oder eine ganze Partition) als virtueller Speicher reserviert. Ein Teil dieses Files wird im Ram gehalten, der Rest bleibt auf Platte. Wird nun eine Speicherstelle benötigt, die nicht im Ram vorhanden ist, so wird sie von Platte eingeladen, und steht dann der CPU zur Verfügung. Dabei kann es sein, daß, um Platz zu schaffen, ein Teil des im Ram gepufferten Speichers wiederum auf Platte ausgelagert wird.
2.1. Kacheln
Zur Verwaltung des virtuellen Speichers wird dieser in Kacheln (oder auch Seiten / Tiles / Pages genannt) eingeteilt, d.h. in Speicherblöcke gleicher Größe. Eine Kachel ist entweder völlig im Ram oder völlig auf Platte.
Der Speicherverwalter führt eine Liste von Puffern in Kachelgröße. Jeder dieser Puffer kann eine Kachel des virtuellen Speichers enthalten. Bei Bedarf wird eine ganze Kachel von Platte geladen oder gespeichert.
Wird für eine bisher ausgelagerte Kachel ein Puffer benötigt, aber keiner frei, wird eine Kachel aus einem der Puffer auf Platte gesichert, um Platz zu schaffen.
2.2. MMU
Um virtuellen Speicher effizient implementieren zu können ist auf jeden Fall eine MMU nötig. Diese übernimmt einen großen Teil der nötigen Verwaltungsarbeit und erlaubt es Programmen, virtuellen Speicher zu gewähren, ohne daß diese für diese Möglichkeit speziell programmiert sein müßten. Dies ist auch der Grund dafür, daß dem Amiga nachträglich noch virtueller Speicher beigefügt werden konnte, obwohl dieser dafür gar nicht vorgesehen war.
2.2.1. Remapping
Die wichtigste Aufgabe der MMU ist es, Adressen, die der Prozessor für seine Speicherzugriffe erzeugt, auf neue Adressen umzusetzen. Dies ist unbedingt nötig, da nur so dem Prozessor der Speicher, der sich in den Puffern befindet, an die Adresse gespiegelt werden kann, an dem er die Kachel erwartet.
Für den Prozessor bzw. die Programme befindet sich der virtuelle Speicher als ein Block im Speicher (ab $08000000). Er greift darauf zu, als ob sich dort Ram befinden würde. Die MMU rechnet nun diese hohen Adressen in die echten (also Pufferadressen um).
Grob beschrieben funktioniert dies wie folgt:
Die MMU trennt die 32Bit Adresse des Prozessors in zwei Teile, einen oberen, der die Nummer der Kachel liefert, und einen niederen, der die Adresse in der Kachel ergibt.
Beispiel, Kachelgröße $1000 Bytes.
CPU: Adresse $08013240
Kachelnummer: $13
Adresse in der Kachel: $0240
Dies geschieht über eine Tabelle, genauer einen Baum, in dem für jede virtuelle Adresse eine reelle gespeichert ist (natürlich für jede Kachel nur einmal, so daß der Aufwand vertretbar bleibt). Dieser Baum residiert im Ram. Die MMU enthält aber einen Cache, in dem die häufigsten Umsetzungen gespeichert sind, so daß normale Speicherzugriffe ohne Zugriffe der MMU auf diesen Baum auskommen.
2.2.2. Bus Error
Was passiert nun mit Kacheln, die sich nicht im Ram befinden, da für diese ja auch keine reelle Adresse ermittelt werden kann. In jedem Tabelleneintrag des MMU-Baums ist ein Bit ("Illegal"-Bit) reserviert. Ist dieses Bit gelöscht, wird, falls eine dieser Adressen angesprochen werden soll, keine Umsetzung vorgenommen, sondern eine Bus-Error-Exception ausgelöst.
Der Exceptionhandler, der den Hauptbestandteil des Speicherverwalters bildet, sorgt nun dafür, daß die betroffene Kachel von Platte geholt wird. Dann wird das "Illegal"-Bit gesetzt, und das Programm mit der auslösendenden Anweisung wieder fortgeführt.
2.2.3. Touched und Modified
Die MMU führt noch zwei weitere Bits für jede Kachel. Das "Modified"-Bit wird jedesmal gesetzt, wenn ein Programm ein Byte einer Kachel verändert. Dieses Bit wird dazu benutzt, um festzustellen, ob eine Kachel, falls sie verdrängt wird, auf Platte gespeichert werden muß oder etwa noch mit dem Platteninhalt identisch ist.
Bei jedem Zugriff des Prozessors auf eine Kachel (lesend oder schreibend) wird zusätzlich noch das "Touched"-Bit gesetzt. Dieses wird dazu benutzt, um festzustellen, welche Kachel mit dem geringsten Nachteil verdrängt werden kann.
2.3. Auslagerungsstrategien
Um keine hohen Performanceverluste durch Seitenflattern (ständiges ein und auslagern einer Seite) zu erleiden, ist es wichtig zu bestimmen, welche Kachel bei Bedarf eines Puffers aus dem Speicher entfernt wird. Die beste Lösung wäre natürlich, die Kachel zu entfernen, die als letztes wieder gebraucht wird. Da es aber unmölich ist dies festzustellen muß man sich mit Algorithmen zufrieden geben, die näherungsweise an diese Leistung herankommen.
2.3.1. FIFO
Bei diesem Verfahren wird diejenige Seite als erstes wieder aus dem Ram entfernt, die als erstes eingeladen wurde. Jede Seite verbleibt also etwa gleich lang im Hauptspeicher. Die Leistungen dieses Verfahrens sind nicht besonders gut, da alle Seiten ohne Rücksicht auf die Häufigkeit ihres Gebrauchs gleich behandelt werden. Dafür ist der Verwaltungsaufwand dieses Verfahrens minimal.
2.3.2. LRU (Least recently used)
Dieses Verfahren nutzt das Phänomen der Lokalität aus. Das bedeutet, daß eine Speicherstelle/Kachel, die in der nahen Vergangenheit häufig angesprochen wurde, auch in der nahen Zukunft wohl häufig benötigt wird (nach diesem Verfahren arbeiten auch gute Caches). Der Nachteil dieses Verfahrens liegt im hohen Verwaltungsaufwand, da theoretisch für jeden Speicherzugriff eine Pufferlistenoperation nötig wäre.
2.3.3. Second chance
Dieses Verfahren ist eine Mischung aus den beiden obengenannten. Es bildet eine gute Näherung für LRU, hat aber dennoch eine Performance, die dem FIFO Verfahren nahekommt. Prinzipiell läuft das Verfahren wie bei FIFO, mit dem Unterschied, daß wenn eine Kachel verdrängt werden soll, erst geprüft wird, ob sie seit dem letzten Mal in Gebrauch war ("Touched"-Bit). Ist dies der Fall, wird das "Touched"-Bit gelöscht, und die Seite wieder oben in den FIFO eingefügt. Verdrängt wird die erste Seite des FIFO, die seit dem letzten Durchlauf nicht benutzt wurde.
Durch Verwendung einer zirkulären Liste anstatt eines FIFOs kann der Verwaltungsaufwand noch einmal gesenkt werden.
3. Implementierung
Der Virtueller-Speicher-Verwalter ist in Cluster implementiert. Die kritischen Stellen (z.B. MMU, Exception Handler) wurden mit Hilfe des Inline- Assemblers codiert.
3.1. MMU und Swapper-Prozeß
Das Programm erzeugt einen MMU-Baum, der ab $08000000 (oder auch an anderer Stelle) einen Bereich als virtuellen Speicher führt. Alle anderen Speicherbereiche werden nicht durch die MMU betroffen. Auf einem Amiga 3000 wird, falls nötig, auch das Kickstart gespiegelt.
Versucht nun eine Task auf einen Speicherplatz zuzugreifen, der nicht im Ram vorhanden ist, löst die MMU eine Bus-Error-Exception aus. Der Exceptionhandler sichert den Exception-Stackframe auf den User-Stack und schaltet das Multitasking wieder an.
Dann wird an den Swapper-Prozeß eine Message gesandt, in der die Adresse des gewünschten Speicherbereichs enthalten ist.
Der Swapper-Prozeß sucht dann einen freien Puffer, und lädt mithilfe von Exec bei einer Partition oder Dos bei einem Swapfile die entsprechende Seite ein.
Dann wird die Message zurückgeschickt. Der wartende Task, schaltet wieder in den Supervisor-Mode, packt den Exception-Stackframe wieder auf den Supervisor-Stack, und kehrt aus der Exception zurück.
3.2. Exec und AllocMem()
Ein Stolperstein findet sich noch in der Exec-Speicherverwaltung. Dort wird zum Schutz der Speicherliste bei Speicheroperationen das Multitasking durch Forbid() unterbunden. Befindet sich aber ein Teil der Speicherliste im auf Platte liegenden Speicher, wird durch den Swapper das Multitasking wieder eingeschaltet (dies muß sein, da sonst weder Device- noch Dos-Funktionen benutzt werden könnten). Versucht nun aber ein anderer Task in dieser Zeit Speicher anzufordern, ist die Liste nicht mehr geschützt und wird mit ziemlicher Sicherheit zerstört.
Dies hätte verhindert werden können, wenn die (der) Entwickler von Exec anstatt eines dummen Forbids eine intelligente Semaphore verwendet hätte, die die Speicherliste sichern würde.
Der Virtueller-Speicher-Verwalter legt nun mit Setfunktion eine derartige Sicherung um die Exec Speicherfunktionen, so daß hier nichts mehr passieren kann.
3.3. Lookahead
Wird immer dann ein Puffer leergeräumt, wenn ein neuer benötigt wird, kann das dazu führen, daß vor jedem Einlagerungsvorgang erst eine Seite geschrieben werden muß. Liegen nun der zu lesende Bereich auf der Platte an einer deutlich anderen Stelle, geht durch die ständige Hin- und Her-Bewegung des Schreib-/Lese-Kopfes viel Arbeitszeit verloren.
Der Speicherverwalter versucht nun immer eine gewisse Menge an Puffern bereitzuhalten, die mit ihrem Bild auf der Platte übereinstimmen, so daß sie nicht erst noch gesichert werden müssen.
Dazu sammelt er bei Bedarf immer eine ganze Anzahl an länger nicht mehr benötigten Kacheln, sortiert sie zur Kopfbewegungsoptimierung, und speichert sie auf Platte.
4. Wie wird es installiert und verwendet
Das Programm verlangt keine aufwendige Installierung. Alle notwendigen Parameter werden als Tooltypes übergeben. Es kann nur von der Workbench aus aufgerufen, aber niemals beendet werden, da es im Amiga System nicht vorgesehen ist, daß Systemspeicher wieder entfernt wird.
4.1. Toolvalues
Folgende Tooltypes werden unterstützt:
SWAPFILE=xxx
Das File oder die Partition, auf die der Speicher ausgelagert werden soll. Eine Partition wird vor Benutzung darauf geprüft, ob sie auch wirklich leer ist (nur bei DOS Partitionen).
FILESIZE=xxx
Die Größe des zu verwendenden Swapfiles in 128KByte blöcken, also z.B. 8 für ein MByte. Bei Partitionen ist diese Angabe unnötig, da die Größe der Partition verwendet wird.
SWAPBUFFER=xxx
Anzahl der zu Verwendenden Puffer. Ein Puffer hat wie eine Kachel 8KByte. Empfehlenswert ist etwa die Hälfte des vorhandenen Speichers dafür zu investieren. Also z.B. 256 Puffer bei 4MByte freiem Ram.
LOOKAHEAD=xxx
Anzahl der Puffer die der Speicherverwalter für die schnelle Bearbeitung bereithalten soll. Sinnvoll sind Werte um etwa ein Achtel der Pufferzahl.
VMEMBASE=xxx
Startadresse des virtuellen Speichers im 4GByte Speicherraum des 68030. Diese Zahl wird als Hexadezimalzahl interpretiert. Voreingestellt ist $08000000, also direkt hinter dem normalen A3000 Fast Ram.
4.2. DMA und Maskenwerte
Ein Problem tritt dann auf, wenn versucht wird, durch einen DMA-Kanal einen Bereich des virtuellen Speichers zu beschreiben. Da DMA Kanäle nicht durch die MMU gefiltert werden, würde dies zur Katastrophe führen. Um dies für Plattenspeicher und ähnliches zu verhindern, besitzen alle Partitionen einen Maskenwert, mit dem der Speicherbereich bestimmt werden kann, in den mit DMA gelesen werden kann. Dies kann mithilfe des OS2.0-Programms HDToolBox vorgenommen werden. Der Maskenwert sollte für alle Partitionen auf 0x07FFFFFF gesetzt werden.
4.3. Workbench-Startup
Für Benutzer, die dauernden Gebrauch von virtuellem Speicher machen wollen, ohne jedesmal das Programm neu starten zu müssen, empfiehlt es sich, dieses in den WBStartup Ordner zu legen. Allerdings muß dann noch der Tooltype "DONOTWAIT=TRUE" gesetzt werden.
4.4. File vs. Partition
Es kann entweder auf ein File oder in eine Partition geswappt werden. Beide Verfahren haben Vor- und Nachteile.
Eine Partition kann nur für diesen Zweck verwendet werden. Dies ist allerdings wegen des geringeren Verwaltungsaufwands wesentlich schneller.
Die Verwendung eines Files ist wesentlich flexibler, hat allerdings einen Filesystem-spezifischen Nachteil. Beim Amiga werden die Verwaltungsblöcke eines Files lediglich verkettet, und nicht wie z.B. in UNIX in einem höherrangigen Speicherblock verwaltet. Dies hat zur Folge, daß, um einen spezifischen Datenblock zu finden, alle Verwaltungsblöcke bis zum zugehörigen durchlaufen werden müssen. Wird ein File nun ziemlich groß (mehrere MB) steigt die Zahl der Verwaltungsblöcke stark an (etwa 30 stück pro MB, also etwa 1000 für 30MB). Damit nun die Performance nicht durch andauernde Seek- Operationen völlig in den Keller geht, sollte man mindestens soviele Puffer für die betroffene Partition vorsehen, wie Verwaltungsblöcke benötigt werden.
Auch zeigen einige Programme aus der Grauzone sauberen Programmierens Probleme mit einem Swapfile. Der Grund dürfte darin liegen, daß dem FileSystem der Partition, auf der sich das Swapfile befindet, ein Puffer, FileNamen oder FileInfoBlock übergeben wird, der zu diesem Zeitpunkt ausgelagert ist. Darauf gibt es natürlich einen Page-Miss, der aber nicht sauber erfüllt werden kann, da das Filesystem selbst auf diese Seite wartet. Der Effekt ist, daß das System für immer wartet.
Dies kann vermieden werden, indem Programmen, die diesen Effekt haben der Zugriff auf die Partition des Swapfiles verboten wird.
5. Wie wird sauber programmiert
Damit es bei der Verwendung von virtuellem Speicher keine Probleme mit eigenen Programmen gibt, müssen einige Richtlinien eingehalten werden.
1.) Fordern sie immer Public-Memory für Interruptspezifische Daten an.
2.) Ebenfalls immer Public-Memory für Ports, Tasks und FileInfoBlocks, IOBuffer sowie Nodes, die sie im System verankern.
3.) Fordern sie nicht einfach den größten im Speicher vorhandenen Block an, da dies zu eventuellen Performanceeinbußen führen kann.
4.) Fordern sie für ihre eigenen Strukturen kein Public-Memory an, da dieses nicht ausgelagert werden kann.
5.) Produzieren sie keine riesigen BSS Hunks, da aller Speicher der bei LoadSeg angefordert wird immer Public ist.
6.) Halten sie die Lokalität ihres Programmes möglichst groß, vermeiden sie also z.B. das Durchhangeln durch riesige Strukturen. Verwenden sie lieber Hashes oder Bäume.
